/**
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * <p>
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
 * 输出：true
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
 * 输出：false
 * <p>
 * 输入：matrix = [], target = 0
 * 输出：false
 *  
 * <p>
 * 提示：
 * <p>
 * m == matrix.length
 * n == matrix[i].length
 * 0 <= m, n <= 100
 * -104 <= matrix[i][j], target <= 104
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(searchMatrix(new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}}, 11));
        // System.out.println(searchMatrix(new int[][]{{1, 1}, {2, 2}}, 0));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int y = matrix.length;
        if (y == 0) {
            return false;
        }
        int x = matrix[0].length;
        if (x == 0) {
            return false;
        }
        for (int i = 0; i < y; i++) {
            if (matrix[i][0] == target) {
                return true;
            } else if (matrix[i][0] > target) {
                if (i != 0) {
                    i -= 1;
                }
                for (int j = 1; j < x; j++) {
                    if (matrix[i][j] == target) {
                        return true;
                    }
                }
                return false;
            } else if (i == y - 1) {
                for (int j = 1; j < x; j++) {
                    if (matrix[i][j] == target) {
                        return true;
                    }
                }
                return false;
            }
        }
        return false;
    }
}